package sort;

/**
 * @author kaho
 * @since 2020/12/14
 */
public class 计数排序 {


    public static void countSort(int[] arr){
        int min = arr[0];
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i]>max) {
                max = arr[i];
            }
            if (arr[i]<min) {
                min = arr[i];
            }
        }

        int[] countArr = new int[max - min + 1];
        for (int i = 0; i < arr.length; i++) {
            ++countArr[arr[i]-min];
        }

        for (int i = 1; i < countArr.length; i++) {
            countArr[i] += countArr[i-1];
        }

        int[] re = new int[arr.length];
        for (int length = arr.length - 1; length > 0; length--) {
            re[--countArr[arr[length] - min]] = arr[length];
        }

        for (int i = 0; i < re.length; i++) {
            arr[i] = re[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,4,5,2,3,5,1,0};
        countSort(arr);
    }

}
